package array;

public class Regex {

	public static boolean match(String s, String matcher) {
		if (s == null || matcher == null) {
			return false;
		}

		if (matcher.equals("*")) {
			return true;
		}

		return match(s, matcher, 0, 0);
	}

	private static boolean match(String s, String matcher, int sp, int mp) {
		boolean matchAny = false;

		while (sp < s.length() && mp < matcher.length()) {
			if (matchAny) {
				if (matcher.charAt(mp) == s.charAt(sp)) {
					if (match(s, matcher, sp, mp)) {
						return true;
					} else {
						sp++;
					}
				} else {
					sp++;
				}
			} else if (matcher.charAt(mp) == '.') {
				sp++;
				mp++;
			} else if (matcher.charAt(mp) == '*') {
				mp++;
				matchAny = true;
			} else if (matcher.charAt(mp) == '+') {
				mp++;
				sp++;
				matchAny = true;
			} else {
				if (matcher.charAt(mp) != s.charAt(sp)) {
					return false;
				} else {
					sp++;
					mp++;
				}
			}
		}

		if (matchAny || mp != matcher.length()) {
			boolean eatAll = true;

			while (mp < matcher.length()) {
				if (matcher.charAt(mp++) != '*') {
					eatAll = false;
					break;
				}
			}

			return eatAll;
		}

		if (sp != s.length()) {
			return false;
		}

		return true;
	}

	public static void main(String[] args) {
		System.out.printf("%s %s: %b\n", "abc", "abc", match("abc", "abc"));
		System.out.printf("%s %s: %b\n", "abc", "bcd", match("abc", "bcd"));
		System.out.printf("%s %s: %b\n", "abc", "abcd", match("abc", "abcd"));
		System.out.printf("%s %s: %b\n", "abcd", "abc", match("abcd", "abc"));
		System.out.printf("%s %s: %b\n", "abc", "a.c", match("abc", "a.c"));
		System.out.printf("%s %s: %b\n", "abc", "ab.", match("abc", "ab."));
		System.out.printf("%s %s: %b\n", "abc", "a.", match("abc", "a."));
		System.out.printf("%s %s: %b\n", "a", "a.", match("a", "a."));
		System.out.printf("%s %s: %b\n", "", "", match("", ""));

		System.out.printf("%s %s: %b\n", "", "+", match("", "+"));
		System.out.printf("%s %s: %b\n", "a", "+", match("a", "+"));
		System.out.printf("%s %s: %b\n", "abc", "+", match("abc", "+"));
		System.out.printf("%s %s: %b\n", "abc", "a+", match("abc", "a+"));
		System.out.printf("%s %s: %b\n", "abc", "ab+", match("abc", "ab+"));
		System.out.printf("%s %s: %b\n", "abc", "abc+", match("abc", "abc+"));
		System.out.printf("%s %s: %b\n", "ac", "a+c", match("ac", "a+c"));
		System.out.printf("%s %s: %b\n", "abc", "a+c", match("abc", "a+c"));
		System.out.printf("%s %s: %b\n", "abbbc", "a+c", match("abbbc", "a+c"));

		System.out.printf("%s %s: %b\n", "", "*", match("", "*"));
		System.out.printf("%s %s: %b\n", "a", "*", match("a", "*"));
		System.out.printf("%s %s: %b\n", "abc", "*", match("abc", "*"));
		System.out.printf("%s %s: %b\n", "abc", "a*", match("abc", "a*"));
		System.out.printf("%s %s: %b\n", "abc", "ab*", match("abc", "ab*"));
		System.out.printf("%s %s: %b\n", "abc", "abc*", match("abc", "abc*"));
		System.out.printf("%s %s: %b\n", "ac", "a*c", match("ac", "a*c"));
		System.out.printf("%s %s: %b\n", "abc", "a*c", match("abc", "a*c"));
		System.out.printf("%s %s: %b\n", "abbbc", "a*c", match("abbbc", "a*c"));

		System.out.printf("%s %s: %b\n", "dccccqz", "dc+",
				match("dccccqz", "dc+"));

	}
}
